package com.lmk.dsa.struct.tree;

import com.lmk.dsa.struct.commons.BstNode;

/**
 * 二叉查找树
 * @param <K>   键
 * @param <V>   值
 * @author LaoMake
 * @since 1.0
 */
public interface BST<K extends Comparable<? super K>, V> {

    /**
     * 获取树中节点的总数
     * @return
     */
    int size();

    /**
     * 获取树的最大高度
     * @return
     */
    int height();

    /**
     * 添加数据节点
     * @param key
     * @param value
     */
    void add(K key, V value);

    /**
     * 添加数据节点
     * @param node
     */
    void add(BstNode<K, V> node);

    /**
     * 获取根节点数据
     * @return
     */
    BstNode<K, V> root();

    /**
     * 获取最小节点
     * @return
     */
    BstNode<K, V> minimum();

    /**
     * 获取最大节点
     * @return
     */
    BstNode<K, V> maximum();

    /**
     * 判断当前树中是否存在指定的key
     * @param key
     * @return
     */
    boolean contains(K key);

    /**
     * 根据指定Key获取节点信息
     * @param key
     * @return
     */
    BstNode<K, V> get(K key);

    /**
     * 根据key删除节点，并返回节点信息。
     * 如果不能存在key，则返回null
     * @param key
     * @return
     */
    BstNode<K, V> remove(K key);

    /**
     * 删除最小节点，并返回节点信息
     * @return
     */
    BstNode<K, V> removeMin();

    /**
     * 删除最大节点，并返回节点信息
     * @return
     */
    BstNode<K, V> removeMax();

    /**
     * 校验当前树是否平衡
     * @return
     */
    boolean isBalanced();
}
